Vertical order traversal of a binary tree [DFS]

Time: O(NLogN); Space: O(N); medium

Given a binary tree, return the vertical order traversal of its nodes values.

For each node at position (X, Y), its left and right children respectively will be at positions (X-1, Y-1) and (X+1, Y-1).

Running a vertical line from X = -infinity to X = +infinity, whenever the vertical line touches some nodes, we report the values of the nodes in order from top to bottom (decreasing Y coordinates).

If two nodes have the same position, then the value of the node that is reported first is the value that is smaller.

Return an list of non-empty reports in order of X coordinate. Every report will have a list of values of nodes.

Example 1:

  3
 / \
9   20
   /  \
  15   7

Input: root = {TreeNode} [3,9,20,null,null,15,7]

Output: [[9],[3,15],[20],[7]]

Explanation:

• Without loss of generality, we can assume the root node is at position (0, 0):

• Then, the node with value 9 occurs at position (-1, -1);

• The nodes with values 3 and 15 occur at positions (0, 0) and (0, -2);

• The node with value 20 occurs at position (1, -1);

• The node with value 7 occurs at position (2, -2).

Example 2:

      1
   /    \
  2      3
 / \    / \
4   5  6   7

Input: root = {TreeNode} [1,2,3,4,5,6,7]

Output: [[4],[2],[1,5,6],[3],[7]]

Explanation:

• The node with value 5 and the node with value 6 have the same position according to the given scheme.

• However, in the report “[1,5,6]”, the node value of 5 comes first since 5 is smaller than 6.

Constraints:

• The tree will have between 1 and 1000 nodes.

• Each node’s value will be between 0 and 1000.

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

1. Depth First Search

import collections

class Solution1(object):
    """
    Time: O(NLogN)
    Space: O(N)
    """
    def verticalTraversal(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        def dfs(node, lookup, x, y):
            if not node:
                return
            lookup[x][y].append(node)
            dfs(node.left, lookup, x-1, y+1)
            dfs(node.right, lookup, x+1, y+1)

        lookup = collections.defaultdict(lambda: collections.defaultdict(list))
        dfs(root, lookup, 0, 0)

        result = []
        for x in sorted(lookup):
            report = []
            for y in sorted(lookup[x]):
                report.extend(sorted(node.val for node in lookup[x][y]))
            result.append(report)
        return result

s = Solution1()

root = TreeNode(3)
root.left, root.right = TreeNode(9), TreeNode(20)
root.right.left, root.right.right = TreeNode(15), TreeNode(7)
assert s.verticalTraversal(root) == [[9],[3,15],[20],[7]]

root = TreeNode(1)
root.left, root.right = TreeNode(2), TreeNode(3)
root.left.left, root.left.right = TreeNode(4), TreeNode(5)
root.right.left, root.right.right = TreeNode(6), TreeNode(7)
assert s.verticalTraversal(root) == [[4],[2],[1,5,6],[3],[7]]

See also:

https://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree